The present invention relates to a process for decoding a sequence of symbols received from a disturbed channel resulting from the convolutional coding of a sequence of information symbols to be transmitted.
Convolutional codes, which are also called convolutive, recurrent, sequential or tree codes are particularly used in space links, which are highly disturbed or interfered with by thermal noise and are effectively protected by using an internal convolutional code concatenated with an external code, generally of the Reed-Solomon type.
The symbols to be transmitted and the symbols of the convolutional code are taken in a q-area alphabet which, in most applications, is the binary alphabet (q=2) because, for larger size alphabets (q&gt;2), the coder and particularly decoder soon become too complex. For these reasons, reference is almost exclusively made to the case where q=2 throughout the remainder of the description. Mention will only be made of the general case (q.noteq.2) when the transposition of the case q=2 to the case q.noteq.2 is not immediate to the Expert.
It is pointed out that a convolutional code is produced by a linear combination of symbols stored in a register supplied and shifted by the symbols to be transmitted. The classic example of a convolutional coder is shown in FIG. 1. This coder comprises two lag or delay elements 2, 4 in series constituting a shift register, a first adder 6 for forming the modulo 2 sum of the information symbol applied to the coder input E and two delayed symbols and a second adder for forming the modulo 2 sum of the information symbol applied to the coder input E and the delayed symbol supplied by delay element 4. The coder input E corresponds to the input of delay element 2. The outputs of the coder are constituted by the outputs of adders 6, 8.
The information symbols enter one by one into the coder of FIG. 1. The introduction of each information symbol leads to the transmission of two coded symbols, obtained by linear combination of the symbol which has just been introduced and two preceding delayed symbols (m in the general case where m.noteq.0). The state of the coder is defined by the vector having as components the delayed symbols.
In general terms, symbols enter k by k into the coder, each of them being applied to the input of a shift register. The introduction of each group of k information symbols leads to the transmission of n coded symbols (n&gt;k) obtained by linear combination of k symbols which have just been introduced and mk preceding delayed symbols (m.noteq.0).
In a conventional manner, the convolutional code is decoded by means of the Viterbi algorithm. This algorithm, which is more particularly described in the article "Error bounds for convolutional codes and an asymptically optimum decoding algorithm", IEEE Trans. on Inf. Theory, IT-13, 1967, pp 260-269 by A. J. VITERBI is an optimum decoding means is the sense of maximum likelihood. It can be interpreted as a means for estimating the sequence of the states of the coder and therefore the sequence of the information symbols, from the sequence of coded symbols, received through a disturbed channel.
Reference will now be made to the principle of the Viterbi algorithm. It is firstly pointed out that as the information symbols are discrete, the number of states is finite. This number is equal to 4 in the case of FIG. 1 and to q.sup.km in general. Thus, the same state can be reached from two states which only differ by the oldest symbol present in the coder memory, because this symbol disappears therefrom as from the shift resulting from the introduction of a new information symbol. This symbol is called the "outgoing symbol" and the two stages (q.sup.k stages in general) leading directly to the considered states are called its antecedents.
If a random effectively reached state is assumed, a decision can be taken with regards to the outgoing symbol, because the subsequently received coded symbols stop definitively depending thereon and therefore obtaining information thereon. The Viterbi algorithm consists of taking a definitive or final decision with regards to the outgoing symbol for each of the possible states. The choice of a single state at each instant is only subsequently determined, following a random number of subsequent decisions, because the advance of the algorithm tends to eliminate any succession of states incompatible with the register structure of the coder.
The operation of the algorithm is conventionally illustrated by the lattice diagram proposed by G. D. FORNEY Jr. in the article "The Viterbi Algorithm", Proc. IEEE, 61, No. 3, March, 1973, pp 268-278.
FIG. 2 is the diagram of the lattice corresponding to the coder of FIG. 1. The integral abscissa represents the time and the integral ordinate each of the states. The thus determined discrete points are called nodes and their abscissa is designated by the node level. The possible transitions between the nodes are represented by branches oriented from left to right (directions of the rising node levels). Any connected sequence of branches, to which corresponds a possible sequence of information symbols and the corresponding sequence of coded symbols is called the path. In the diagram, the branches in continuous lines and broken lines respectively represent the information symbols 0 and 1. The pairs of bits associated with each branch are corresponding coded symbols.
The decoding of a sequence of coded symbols received is translated in this representation of the algorithm by the determination of the best path for the likelihood criterion. For each node, the highest likelihood path converging there is determined and all that is left is the maximum likelihood path.
The known algorithm described hereinbefore makes it possible to obtain the best possible estimate of the sequence of states and therefore of the sequence of information symbols. However, this process gives no information on the reliability of the givan information symbols. However, this information makes it possible to improve decoding in certain special cases, which are particularly of interest for space links.
It has already been stated that in this case use is made of an internal convolutional code concatenated with an external code of the Reed-Solomon type. Following the decoding of the convolutional code, the residual errors are generally grouped in short packets corrected by the Reed-Solomon code with a particular efficiency. However, the decoding of the external code can be greatly improved if these error packets are localized and more particularly if the symbols to be decoded are weighted as a function of their reliability.
This reliability information is available in principle, because any demodulation or decoding decision can be interpreted as deduced from a comparison of the probabilities of the various possible hypotheses. Thus, the only problem is to make this information explicit. Moreover, an overall estimate of the reliability of the decision relating to a long sequence of information symbols would hardly be useful because, in the case of concatenated decoding, it is at least wished to locate the residual error packets.
The weighting of decoded symbols is already known per se in the case of linear codes, which include convolutional codes. For a complete description, reference can e.g. be made to the article "Decodage par repliques" which appeared in Annales des Telecommunications, vol. 31, No. 11-12, Nov.-Dec. 1976, pp 387-404 by G. Battail and M. Decouvelaere.
The conventional putting into use of the Viterbi algorithm consists of associating two memories with each of the possible states. One of them contains the best sequence of information symbols leading to this state and which is called the survivor. The other contains a measurement of the cumulative likelihood of this sequence. The content of the memories is deduced from that of the memories associated with the antecedent node located on the best path. The cumulative likelihood is modified by the addition of that of the branch leading to the considered node. The sequence of symbols is copied out and increased by the final determined symbol. In order to avoid the need of keeping in the memory a sequence of symbols whose length increases indefinitely with time, use is made of a register of adequate length L, where the content of the preceding register is transferred and shifted by the introduction of the final determined symbol (reference will be made hereinafter to the term "shifted transfer" to designate this operation). The symbols leaving the registers associated with the different states are almost always identical (if the register is long enough) and their sequence constitutes the definitive result of the decoding.
Details will now be given as to how symbol-by-symbol weighting is obtained. This known weighting will be described in the particular case where the symbols are binary and are designated "0" and "1". Thus, the decoder output can simply be connected to that of one of the registers associated with the states and chosen in an arbitrary manner. However, it is preferable to take as the decoded information symbol, the result of a majority decision on all the symbols simultaneously leaving the registers associated with the states (reference can be made in this connection to the book by A. J. Viterbi and J. K. Omura "Principles of Digital Communication and Coding", McGraw-Hill, 1979).
For a given node, the difference between the cumulative likelihoods of the two paths leading thereto is equal to the algebraic value of the outgoing symbol, by the very definition of this magnitude, i.e. the logarithm of the ratio of the probabilities of realizing the two hypotheses "0 transmitter" and "1 transmitter". Its sign consequently indicates which is the determined symbol ("+" corresponds to "0" and "-" to "1"), while its absolute value measures the reliability of the decision taken. In particular, it is zero in the case of indeterminacy where these two probabilities are equal. A weighting of the desired form is obtained by placing in the memory for each state, the sequence of the algebraic values calculated in this way instead of the sequence of symbols only.
Thus, the same number of sequences of algebraic values are obtained as there are possible states. Then, as in the algorithm in its conventional form, it is possible only to retain the sequence of algebraic values associated with each survivor, so that nothing is changed in the shifted transfer, except that the symbols are replaced by real numbers. This simple solution is not completely satisfactory. Thus, the choice of the outgoing symbol from a node can be taken with a small margin, whereas the sequences of algebraic values associated with each of the paths converging there can be very different.